package com.sise.Tree;

/**
 *      108. 将有序数组转换为二叉搜索树
 *
 *      给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。
 *      高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 的二叉树。
 *
 *      题解：由于题目中给出的是 升序数组，故此可以联想到 中序遍历（左根右），故此中心点便是 根节点，
 *           使用 mid = (left + right) / 2 即可。
 *           根据 根节点 分为左右子树，返回值为 子树节点
 *
 *          1、返回值：递归节点
 *          2、动作：创建当前层节点，连接左右子树
 *          3、终止条件：数组左边大于右边
 */
public class _108_sortedArrayToBST {
    public TreeNode sortedArrayToBST(int[] nums) {
        return build(nums, 0, nums.length - 1);
    }

    private TreeNode build(int[] nums, int left, int right){
        if (left > right) return null;

        int mid = (left + right) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = build(nums, left, mid - 1);
        root.right = build(nums, mid + 1, right);
        return root;
    }
}
